home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 076-100 / disk_087 / diff / diff.c < prev   
C/C++ Source or Header  |  1992-05-06  |  5KB  |  311 lines
  1. /* diff  - print differences between 2 files      Author: Erik Baalbergen */
  2.  
  3. /* Poor man's implementation of diff(1)
  4.  - no options available
  5.  - may give more output than other diffs, due to the straight-forward algorithm
  6.  - runs out of memory if the differing chunks become too large
  7.  - input line length should not exceed LINELEN; longer lines are truncated,
  8.    while only the first LINELEN characters are compared
  9.  
  10.  Please report bugs and suggestions to erikb@cs.vu.nl
  11. */
  12. #include "stdio.h"
  13. FILE *fopen();
  14.  
  15. #define LINELEN 128
  16.  
  17. char *prog;
  18. int diffs = 0;
  19.  
  20. main(argc, argv)
  21.     char **argv;
  22. {
  23.     FILE *fp1 = NULL, *fp2 = NULL;
  24.  
  25.     prog = *argv++;
  26.     if (argc != 3)
  27.         fatal("use: %s file1 file2", prog);
  28.     if (strcmp(argv[0], "-") == 0)
  29.         fp1 = stdin;
  30.     else
  31.     if (strcmp(argv[1], "-") == 0)
  32.         fp2 = stdin;
  33.     if (fp1 == NULL && (fp1 = fopen(argv[0], "r")) == NULL)
  34.         fatal("can't read %s", argv[0]);
  35.     if (fp2 == NULL && (fp2 = fopen(argv[1], "r")) == NULL)
  36.         fatal("can't read %s", argv[1]);
  37.     diff(fp1, fp2);
  38.     exit(diffs > 0);
  39. }
  40.  
  41. fatal(fmt, s)
  42.     char *fmt, *s;
  43. {
  44.     fprintf(stderr, "%s: ", prog);
  45.     fprintf(stderr, fmt, s);
  46.     fprintf(stderr, "\n");
  47.     exit(2);
  48. }
  49.  
  50. /* the line module */
  51. char *malloc();
  52. char *fgets();
  53.  
  54. struct line {
  55.     struct line *l_next;
  56.     char l_text[LINELEN + 2];
  57. };
  58.  
  59. struct line *freelist = 0;
  60.  
  61. struct line *
  62. new_line()
  63. {
  64.     register struct line *l;
  65.  
  66.     if (l = freelist)
  67.         freelist = freelist->l_next;
  68.     else
  69.     if ((l = (struct line *)malloc(sizeof(struct line))) == 0)
  70.         fatal("out of memory");
  71.     return l;
  72. }
  73.  
  74. free_line(l)
  75.     register struct line *l;
  76. {
  77.     l->l_next = freelist;
  78.     freelist = l;
  79. }
  80.  
  81. #define equal_line(l1, l2) (strcmp((l1)->l_text, (l2)->l_text) == 0)
  82.  
  83. int equal_3(l1, l2)
  84.     struct line *l1, *l2;
  85. {
  86.     register int i;
  87.  
  88.     for (i=0; i<3 && l1 && l2; ++i, l1=l1->l_next, l2=l2->l_next) {
  89.         if (!equal_line(l1, l2))
  90.             return 0;
  91.     }
  92.     return (i==3);
  93. }
  94.  
  95. struct line *
  96. read_line(fp)
  97.     FILE *fp;
  98. {
  99.     register struct line *l = new_line();
  100.     register char *p;
  101.     register int c;
  102.  
  103.     (p = &(l->l_text[LINELEN]))[1] = '\377';
  104.     if (fgets(l->l_text, LINELEN + 2, fp) == NULL) {
  105.         free_line(l);
  106.         return 0;
  107.     }
  108.     if (p[1] != '\377' && *p != '\n') {
  109.         while ((c = fgetc(fp)) != '\n' && c != EOF) {}
  110.         *p++ = '\n';
  111.         *p = '\0';
  112.     }
  113.     l->l_next = 0;
  114.     return l;
  115. }
  116.  
  117. /* file window handler */
  118. struct f {
  119.     struct line *f_bwin, *f_ewin;
  120.     struct line *f_aside;
  121.     int f_linecnt;    /* line number in file of last advanced line */
  122.     FILE *f_fp;
  123. };
  124.  
  125. advance(f)
  126.     register struct f *f;
  127. {
  128.     register struct line *l;
  129.     
  130.     if (l = f->f_bwin) {
  131.         if (f->f_ewin == l)
  132.             f->f_bwin = f->f_ewin = 0;
  133.         else
  134.             f->f_bwin = l->l_next;
  135.         free_line(l);
  136.         (f->f_linecnt)++;
  137.     }
  138. }
  139.  
  140. aside(f, l)
  141.     struct f *f;
  142.     struct line *l;
  143. {
  144.     register struct line *ll;
  145.  
  146.     if (ll = l->l_next) {
  147.         while (ll->l_next)
  148.             ll = ll->l_next;
  149.         ll->l_next = f->f_aside;
  150.         f->f_aside = l->l_next;
  151.         l->l_next = 0;
  152.         f->f_ewin = l;
  153.     }
  154. }
  155.  
  156. struct line *
  157. next(f)
  158.     register struct f *f;
  159. {
  160.     register struct line *l;
  161.  
  162.     if (l = f->f_aside) {
  163.         f->f_aside = l->l_next;
  164.         l->l_next = 0;
  165.     }
  166.     else
  167.         l = read_line(f->f_fp);
  168.     if (l) {
  169.         if (f->f_bwin == 0)
  170.             f->f_bwin = f->f_ewin = l;
  171.         else {
  172.             f->f_ewin->l_next = l;
  173.             f->f_ewin = l;
  174.         }
  175.     }
  176.     return l;
  177. }
  178.  
  179. init_f(f, fp)
  180.     register struct f *f;
  181.     FILE *fp;
  182. {
  183.     f->f_bwin = f->f_ewin =  f->f_aside = 0;
  184.     f->f_linecnt = 0;
  185.     f->f_fp = fp;
  186. }
  187.  
  188. update(f, s)
  189.     register struct f *f;
  190.     char *s;
  191. {
  192.     while (f->f_bwin && f->f_bwin != f->f_ewin) {
  193.         printf("%s%s", s, f->f_bwin->l_text);
  194.         advance(f);
  195.     }
  196. }
  197.     
  198. /* diff procedure */
  199. diff(fp1, fp2)
  200.     FILE *fp1, *fp2;
  201. {
  202.     struct f f1, f2;
  203.     struct line *l1, *s1, *b1, *l2, *s2, *b2;
  204.     register struct line *ll;
  205.  
  206.     init_f(&f1, fp1);
  207.     init_f(&f2, fp2);
  208.     l1 = next(&f1);
  209.     l2 = next(&f2);
  210.     while (l1 && l2) {
  211.         if (equal_line(l1, l2)) {
  212. equal:
  213.             advance(&f1);
  214.             advance(&f2);
  215.             l1 = next(&f1);
  216.             l2 = next(&f2);
  217.             continue;
  218.         }
  219.         s1 = b1 = l1;
  220.         s2 = b2 = l2;
  221.         /* read several more lines */
  222.         next(&f1); next(&f1);
  223.         next(&f2); next(&f2);
  224.         /* start searching */
  225. search:
  226.         if ((l2 = next(&f2)) == 0)
  227.             continue;
  228.         ll = s1;
  229.         b2 = b2->l_next;
  230.         do {
  231.             if (equal_3(ll, b2)) {
  232.                 aside(&f1, ll);
  233.                 aside(&f2, b2);
  234.                 differ(&f1, &f2);
  235.                 goto equal;
  236.             }
  237.         } while (ll = ll->l_next);
  238.         if ((l1 = next(&f1)) == 0)
  239.             continue;
  240.         ll = s2;
  241.         b1 = b1->l_next;
  242.         do {
  243.             if (equal_3(ll, b1)) {
  244.                 aside(&f2, ll);
  245.                 aside(&f1, b1);
  246.                 differ(&f1, &f2);
  247.                 goto equal;
  248.             }
  249.         } while (ll = ll->l_next);
  250.         goto search;
  251.     }
  252.     /* one of the files reached EOF */
  253.     if (l1) /* eof on 2 */
  254.         while (next(&f1)) {}
  255.     if (l2)
  256.         while (next(&f2)) {}
  257.     f1.f_ewin = 0;
  258.     f2.f_ewin = 0;
  259.     differ(&f1, &f2);
  260. }
  261.  
  262. differ(f1, f2)
  263.     register struct f *f1, *f2;
  264. {
  265.     int cnt1 = f1->f_linecnt, len1 = wlen(f1), cnt2 = f2->f_linecnt,
  266.         len2 = wlen(f2);
  267.  
  268.     if ((len1 = wlen(f1)) || (len2 = wlen(f2))) {
  269.         if (len1 == 0) {
  270.             printf("%da", cnt1);
  271.             range(cnt2 + 1, cnt2 + len2);
  272.         }
  273.         else
  274.         if (len2 == 0) {
  275.             range(cnt1 + 1, cnt1 + len1);
  276.             printf("d%d", cnt2);
  277.         }
  278.         else {
  279.             range(cnt1 + 1, cnt1 + len1);
  280.             putchar('c');
  281.             range(cnt2 + 1, cnt2 + len2);
  282.         }
  283.         putchar('\n');
  284.         if (len1)
  285.             update(f1, "< ");
  286.         if (len1 && len2)
  287.             printf("---\n");
  288.         if (len2)
  289.             update(f2, "> ");
  290.         diffs++;
  291.     }
  292. }
  293.  
  294. wlen(f)
  295.     struct f *f;
  296. {
  297.     register cnt = 0;
  298.     register struct line *l = f->f_bwin, *e = f->f_ewin;
  299.  
  300.     while (l && l != e) {
  301.         cnt++;
  302.         l = l->l_next;
  303.     }
  304.     return cnt;
  305. }
  306.  
  307. range(a, b)
  308. {
  309.     printf(((a == b) ? "%d" : "%d,%d"), a, b);
  310. }
  311.